/**
 * 1. 手写Object.create
 *    思想：将传入的对象作为原型
 */
function create(obj) {
  function F() {}
  F.prototype = obj;
  return new F();
}

/**
 * 2. instanceof
 *    用于判断构造函数的 prototype 属性是否出现在对象的原型链上。
 */
function myInstanceof(left, right) {
  let proto = Object.getPrototypeOf(left), //获取对象的原型
    prototype = right.prototype; //构造函数原型

  while (true) {
    if (!proto) return false;
    if (proto === prototype) return true;
    proto = Object.getPrototypeOf(proto);
  }
}

/**
 * 3. new
 */
function mynew(constructor, ...args) {
  const obj = {}; //等价于Object.create(constructor.prototype)
  obj.__proto__ = constructor.prototype;
  const res = constructor.apply(obj, args); //拿到返回值
  // 如果构造函数没有显式return（通常情况）那么person就是新创建的对象obj
  // 如果构造函数返回的不是一个对象，比如1、"abc" 那么person还是新创建的对象obj
  // 如果构造函数显式返回了一个对象，比如{}、function() {}
  // 那么person就不是新创建的对象obj了，而是显式return的这个对象
  return res instanceof Object ? res : obj;
}

/**
 * 4. 防抖
 *    事件被触发 n 秒后再执行回调，如果在这 n 秒内事件又被触发，则重新计时。
 */
function debounce(fn, wait) {
  let timer = null;
  return function () {
    let context = this,
      args = arguments;
    // 如果存在定时器就取消之前的定时器重新计时
    if (timer) {
      clearTimeout(timer);
      timer = null;
    }
    timer = setTimeout(() => {
      fn.apply(context, args);
    }, wait);
  };
}

/**
 * 5. 节流
 *    在规定的单位时间内，只能有一次触发事件的回调函数执行，如果在同一个单位时间内某事件被触发多次，只有一次能生效。
 */

function throttle(fn, delay) {
  let timer = null;
  return function (...args) {
    // 最多执行一次
    if (!timer) {
      timer = setTimeout(() => {
        fn.call(this, ...args);
        timer = null;
      }, delay);
    }
  };
}

/**
 * 6. 类型判断函数
 */
function getType(value) {
  // 判断数据是null的情况
  if (value === null) {
    return value + "";
  }
  // 判断数据是引用数据类型的情况
  if (typeof value === "object") {
    let valueClass = Object.prototype.toString.call(value),
      type = valueClass.split(" ")[1].split("");
    type.pop();
    return type.join("").toLowerCase();
  } else {
    return typeof value;
  }
}

/**
 * 7. call
 */
// @ts-ignore
Function.prototype.myCall = function (context = window, ...args) {
  // 判断调用对象
  if (typeof this !== "function") {
    console.log("type error");
  }
  context.fn = this;
  let result = context.fn(...args);
  delete context.fn;
  return result;
};
const person = {
  fullName(city, country) {
    return this.firstName + " " + this.lastName + "," + city + "," + country;
  },
};
const person1 = {
  firstName: "Bill",
  lastName: "Gates",
};
console.log(person.fullName.myCall(person1, "zzd", "lwh"));

/**
 * 8. apply
 */
Function.prototype.myApply = function (context = window, array = []) {
  // 判断调用对象
  if (typeof this !== "function") {
    console.log("error");
  }
  context.fn = this;
  let res = context.fn(...array);
  delete context.fn;
  return res;
};

/**
 * 9. bind
 *    函数内部使用 apply 来绑定函数调用，需要判断函数作为构造函数的情况，
 *    这个时候需要传入当前函数的 this 给 apply 调用，其余情况都传入指定的上下文对象。
 */
Function.prototype.myBind = function (context) {
  // 判断调用对象
  if (typeof this !== "function") {
    console.log("error");
  }
  // 获取参数
  let args = [...arguments].slice(1),
    fn = this;
  return function Fn() {
    // 根据调用方式，传入不同的绑定值
    return fn.apply(
      this instanceof Fn ? this : context,
      args.concat(...arguments)
    );
  };
};

/**
 * 10. 函数柯里化
 */
function curry(fn) {
  let len = fn.length;
  return function temp() {
    let args = [...arguments];
    if (args.length >= len) {
      return fn(...args);
    } else {
      return function () {
        return temp(...args, ...arguments);
      };
    }
  };
}

/**
 * 11. 浅拷贝
 *      对象浅拷贝：
 *      (1)Object.assign()
 *      (2)扩展运算符
 *      数组浅拷贝：
 *      (1)Array.prototype.slice
 *      (2)Array.prototype.concat
 *      (3)手写实现
 */
function shallowCopy(object) {
  // 只拷贝对象
  if (!object || typeof object !== "object") return;
  // 新建数组还是对象
  let newObj = Array.isArray(object) ? [] : {};
  // 遍历object，并且判断是object的属性才拷贝
  for (let key in object) {
    if (object.hasOwnProperty(key)) {
      newObj[key] = object[key];
    }
  }
  return newObj;
}

/**
 * 12. 深拷贝
 *     (1)JSON.stringify()存在问题，拷贝的对象中如果有函数，
 *      undefined，symbol，当使用过JSON.stringify()进行处理之后，都会消失。
 *     (2)lodash的_.cloneDeep()
 *     (3)手写深拷贝
 */
function deepCopy(object) {
  if (!object || typeof object !== "object") return;
  let newObj = Array.isArray(object) ? [] : {};
  for (let key in object) {
    if (object.hasOwnProperty(key)) {
      newObj[key] =
        typeof object[key] === "object" ? deepCopy(object[key]) : object[key];
    }
  }
  return newObj;
}

/**
 * 13. Promise
 */
function MyPromise(executor) {
  this.status = "pending";
  this.value = null;
  this.reason = null;
  // 把then的onFullfilled方法保存，resolve的时候执行
  this.onFullfilledArray = [];
  this.onRejectedArray = [];

  const resolve = (value) => {
    if (value instanceof MyPromise) {
      return value.then(resolve, reject);
    }
    setTimeout(() => {
      if (this.status === "pending") {
        this.value = value;
        this.status = "fulfilled";
        this.onFullfilledArray.forEach((func) => {
          func(value);
        });
      }
    });
  };

  const reject = (reason) => {
    setTimeout(() => {
      if (this.status === "pending") {
        this.reason = reason;
        this.status = "rejected";
        this.onRejectedArray.forEach((func) => {
          func(reason);
        });
      }
    });
  };

  // 在合适的时机调用
  try {
    executor(resolve, reject);
  } catch (e) {
    reject(e);
  }
}

MyPromise.prototype.then = function (onFullfilled, onRejected) {
  onFullfilled =
    typeof onFullfilled === "function" ? onFullfilled : (data) => data;
  onRejected =
    typeof onRejected === "function"
      ? onRejected
      : (error) => {
          throw error;
        };
  // 将promise2作为返回值
  let promise2
  if (this.status === "fulfilled") {
    return promise2 = new MyPromise((resolve, reject) => {
        setTimeout(() => {
            try {
                let result = onFullfilled(this.value)
                resolvePromise(promise2, result, resolve,reject)
            } catch (e) {
                reject(e)
            }
        });
    })
    onFullfilled(this.value);
  }
  if (this.status === "rejected") {
    return promise2 = new MyPromise((resolve, reject) => {
        setTimeout(() => {
            try {
                //这个新的promise2 reject的值为onrejected的执行结果
                let result = MyPromise(this.reason)
                resolvePromise(promise2, result, resolve,reject)
            }
            catch (e) {
                reject(e)
            }
        })
    })
  }
  // then方法是同步的，此时保存开发者定义的方法
  if (this.status === "pending") {
    return promise2 = new MyPromise((resolve, reject) => {
        this.onFullfilledArray.push(() => {
            try {
                let result = MyPromise(this.value)
                resolvePromise(promise2, result, resolve,reject)
            }
            catch (e) {
                reject(e)
            }
        })
        this.onRejectedArray.push(() => {
            try {
                let result = MyPromise(this.reason)
                resolvePromise(promise2, result, resolve,reject)
            }
            catch (e) {
                reject(e)
            }
        })
    })
  }
};

let promise1 = new MyPromise((resolve, reject) => {
  setTimeout(() => {
    resolve("data");
  }, 1000);
});
promise1.then((data) => {
  console.log(data);
});
promise1.then((data) => {
  console.log(`${data}--2`);
});

const resolvePromise = (promise2, result, resolve, reject) => {
    //当result和promise2相等时，也就是在onfullfilled返回promise2时，执行reject
    if (result === promise2) {
        reject(new TypeError('error due to circular reference'))
    }
    //是否已经执行过onfullfilled或onrejected
    let consumed = false
    let thenable
    if (result instanceof MyPromise) {
        if(result.status === 'pending') {
            result.then(function (data) {
                resolvePromise(promise2,data,resolve,reject)
            },reject)
        } else {
            result.then(resolve,reject)
        }
        return
    }
    let isComplexResult = target => (typeof target === 'function' || typeof target === 'object')
    && (target !== null)
    //如果返回的是疑似promise类型
    if (isComplexResult(result)) {
        try {
            thenable = result.then
            //判断返回值是否是promise类型
            if (typeof thenable ===  'function') {
                thenable.call(result, function (data) {
                    if (consumed) return
                    consumed = true
                    return resolvePromise(promise2,data,resolve,reject)
                }, function (error) {
                    if (consumed) return
                    consumed = true
                    return reject(error)
                })
            }
            else {
                resolve(result)
            }
        } catch (e) {
            if(consumed) return
            consumed = true
            return reject(e)
        }
    }
    else {
        resolve(result)
    }
}

MyPromise.prototype.catch = function(fn) {
    return this.then(null, fn)
}
MyPromise.resolve = function(value) {
    return new MyPromise((resolve, reject) => {
        resolve(value)
    })
}
MyPromise.reject = function(value) {
    return new MyPromise((resolve, reject) => {
        reject(value)
    })
}
MyPromise.all = function(promiseArray) {
    if(!Array.isArray(promiseArray)) return
    return new MyPromise((resolve, reject) => {
        try {
            let resArr = []
            const length = promiseArray.length
            for(let i = 0; i < length; i++) {
                promiseArray[i].then(data => {
                    resArr.push(data)
                    if(resArr.length === length) {
                        resolve(resArr)
                    }
                }, reject)
            }
        } catch (e) {
            reject(e)
        }
    })
}
MyPromise.race = function(promiseArray) {
    if(!Array.isArray(promiseArray)) return
    return new MyPromise((resolve, reject) => {
        try {
            const length = promiseArray.length
            for(let i = 0; i < length; i++) {
                promiseArray[i].then(resolve, reject)
            }
        } catch (e) {
            reject(e)
        }
    })
}

/**
 * 14. AJAX
 */
function ajax(url) {
    return new Promise((resolve, reject) => {
        const xhr = new XMLHttpRequest()
        // 第三个指定是否异步
        xhr.open('GET', url, true)
        xhr.onreadystatechange = function() {
            if(xhr.readyState === 4) {
                if(xhr.status === 200) {
                    resolve(JSON.stringify(xhr.responseText))
                } else {
                    reject('error')
                }
            }
        }
        xhr.send(null)
    })
}

/**
 * 15. 手撕快排
 */
const _quickSort = array => {
    quickSort(array, 0, array.length - 1)
    return array
}
const quickSort = (array, start, end) => {
    // 注意递归边界条件
    if(end - start < 1) return
    // 取第一个最为基准
    const base = array[start]
    let left = start, right = end
    while(left < right) {
        // 从右往左找小于基准元素的数，赋值给右指针
        while(left < right && array[right] >= base) right--
        array[left] = array[right]
        // 从左往右找大于基准元素的数，赋值给左指针
        while(left < right && array[left] <= base)    left++
        array[right] = array[left]
    }
    // 双指针重合处，将基准元素填到这个位置。基准元素已经事先保存下来了，因此不用担心上面的赋值操作会覆盖掉基准元素的值
    // array[left] 位置已经确定，左边的都比它小，右边的都比它大
    array[left] = base
    quickSort(array, start, left - 1)
    quickSort(array, left + 1, end)
    return array
}

// console.log(_quickSort([2,5,2,7,8,0,1,9]));
/**
 * 16. JSONP
 */
function addScript(src) {
    const script = document.createElement('script')
    script.src = src
    document.body.appendChild(script)
}
// 传参一个回调函数名给后端，方便后端返回时执行这个在前端定义的回调函数
// addScript("http://xxx.xxx.com/xxx.js?callback=handleRes")
// 设置一个全局callback函数来接收回调结果
function handleRes(res) {
    console.log(res)
}
// 服务端返回如下（返回时即执行全局函数）：
// handleRes({"success": true, "user": "admin"})

/**
 * 17. 寄生组合继承
 */
// 父
function Super(name) {
    this.name = name
    this.say = () => {
        console.log('hhh');
    }
}
Super.prototype.play = () => {
    console.log('yyy');
}
// 子
function Sub(name, age) {
    Super.call(this, name)
    this.age = age
}
Sub.prototype = Object.create(Super.prototype)
Sub.prototype.constructor = Sub

/**
 * 18. 实现日期格式化函数
 */
//  dateFormat(new Date('2020-12-01'), 'yyyy/MM/dd') // 2020/12/01
//  dateFormat(new Date('2020-04-01'), 'yyyy/MM/dd') // 2020/04/01
//  dateFormat(new Date('2020-04-01'), 'yyyy年MM月dd日') // 2020年04月01日
function dateFormat(dateInput, format) {
  let day = dateInput.getDate()
  let month = dateInput.getMounth() + 1
  let year = dateInput.getFullYear()
  format = format.replace(/yyyy/, year)
  format = format.replace(/MM/, month)
  format = format.replace(/dd/, day)
  return format
}

/**
 * 19. 实现数组乱序输出
 *     取出数组的第一个元素，随机产生一个索引值，将该第一个元素和这个索引对应的元素进行交换。
       第二次取出数据数组第二个元素，随机产生一个除了索引为1的之外的索引值，并将第二个元素与该索引值对应的元素进行交换
       按照上面的规律执行，直到遍历完成
 */
function randomArr(arr) {
  for(let i = 0; i < arr.length; i++) {
    const randomIndex = Math.round(Math.random() * (arr.length - 1 - i)) + i;
    [arr[i], arr[randomIndex]] = [arr[randomIndex], arr[i]]
  }
  return arr
}  
// console.log(randomArr([1,4,2,3,4,1,2]));

/**
 * 20. 数组求和
 */
function sumArr(arr) {
  return arr.reduce((total, i) => {
    return total += i
  }, 0)
}
// console.log(sumArr([1,2,3]));

/**
 * 21. 数组扁平化
 */
// 1. 递归实现
let arr = [1,[2,[3,4,5]]]
function flatten1(arr) {
  let res = []
  for(let i = 0; i < arr.length; i++) {
    if(Array.isArray(arr[i])) {
      res = res.concat(flatten1(arr[i]))
    } else {
      res.push(arr[i])
    }
  }
  return res
}
// 2. reduce
function flatten2(arr) {
  return arr.reduce((prev, next) => prev.concat(Array.isArray(next) ? flatten2(next) : next), [])
}
// 3. 扩展运算符
function flatten3(arr) {
  while(arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr)
  }
  return arr
}
// console.log(flatten3(arr));
// 4.flat   arr.flat([depth])
function flatten4(arr) {
  return arr.flat(Infinity)
}

/**
 * 22. 数组去重
 */
//1. Set
function uniqueArr(arr) {
  return [...new Set(arr)]
}
// console.log(uniqueArr([1,1,1,2,3,4,4]));
//2. map
function uniqueArr2(arr) {
  let map = {}, res = []
  for(let i = 0; i < arr.length; i++) {
    if(!map.hasOwnProperty(arr[i])) {
      map[arr[i]] = 1
      res.push(arr[i])
    }
  }
  return res
}

/**
 * 23. 数组flat方法
 */
function _flat(arr, depth) {
  if(!Array.isArray(arr) || depth <= 0) return arr
  return arr.reduce((prev, next) => {
    if(Array.isArray(next)) {
      return prev.concat(_flat(next, depth-1))
    } else {
      return prev.concat(next)
    }
  },[])
}

/**
 * 24. 数组filter方法
 */
Array.prototype._filter = function(fn) {
  if(typeof fn !== 'function') {
    throw Error('参数必须是函数')
  }
  const res = []
  for(let i = 0, len = this.length; i < len; i++) {
    fn(this[i]) && res.push(this[i])
  }
  return res
}

/**
 * 25. 数组map方法
 */
Array.prototype._map = function(fn) {
  if(typeof fn !== 'function') {
    throw Error('参数必须是函数')
  }
  const res = []
  for(let i = 0, len = this.length; i < len; i++) {
    res.push(fn(this[i]))
  }
  return res
}

/**
 * 26. 字符串repeat方法
 */
function repeat(s, n) {
  return (new Array(n+1)).join(s)
}

/**
 * 27. 数字千分位用逗号隔开，数字有小数
 */
let formatNum = n => {
  let num = n.toString(), decimals = ''
  num.indexOf('.') > -1 ? decimals = num.split('.')[1] : decimals
  let len = num.length
  if(len <= 3) {
    return num
  } else {
    let temp = '', remainder = len % 3  // 别忘了小数点的长度
    // 小数部分
    decimals ? temp = '.' + decimals : temp
    if(remainder > 0) {
      // 不是3的整数倍
      return num.slice(0, remainder) + ',' + num.slice(remainder, len).match(/\d{3}/g).join(',') + temp
    } else {
      return num.slice(0, len).match(/\d{3}/g).join(',') + temp
    }
  }
}
// console.log(formatNum(98765432.23));

/**
 * 28. 类数组转换为数组
 *     1.Array.prototype.silce.call(arraylike)
 *     2.Array.prototype.splice.call(arraylike, 0)
 *     3.Array.prototype.concat.apply([], arrayLike);
 *     4.Array.from(arrayLike);
 */

/**
 * 29. 将js对象转换为树形结构
 *     转换前：
        source = [{
                    id: 1,
                    pid: 0,
                    name: 'body'
                  }, {
                    id: 2,
                    pid: 1,
                    name: 'title'
                  }, {
                    id: 3,
                    pid: 2,
                    name: 'div'
                  }]
        // 转换为: 
        tree = [{
                  id: 1,
                  pid: 0,
                  name: 'body',
                  children: [{
                    id: 2,
                    pid: 1,
                    name: 'title',
                    children: [{
                      id: 3,
                      pid: 1,
                      name: 'div'
                    }]
                  }
                }]
 */
function jsonToTree(data) {
  // 初始化结果数组，并判断输入数据的格式
  let res = []
  if(!Array.isArray(data)) return res
  // 使用map将当前对象的id与当前对象对应存储起来
  let map = {}
  data.forEach(item => {
    map[item.id] = item
  })
  data.forEach(item => {
    let parent = map[item.pid]
    if(parent) {
      (parent.children || (parent.children = [])).push(item)
    } else {
      res.push(item)
    }
  })
  return res
}

/**
 * 30.解析URL参数为对象
 */
let url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'
/* 结果
{ user: 'anonymous',
  id: [ 123, 456 ], // 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
  city: '北京', // 中文需解码
  enabled: true, // 未指定值的 key 约定为 true
}
*/

function parseParam(url) {
  const paramsStr = /.+\?(.+)$/.exec(url)[1]   // 将 ? 后面的字符串取出来
  // console.log(paramsStr);
  const paramArr = paramsStr.split('&')
  // console.log(paramArr);
  let paramsObj = {}
  paramArr.forEach(param => {
    if(/=/.test(param)) {    // 处理有 value 的参数
      let [key, val] = param.split('=')
      val = decodeURIComponent(val)   // 解码
      val = /^\d+$/.test(val) ? parseFloat(val) : val
      if(paramsObj.hasOwnProperty(key)) {
        paramsObj[key] = [].concat(paramsObj[key], val)
      } else {
        paramsObj[key] = val
      }
    } else {
      // 没有value值设为true
      paramsObj[param] = true
    }
  })
  return paramsObj
}
// console.log(parseParam(url));

/**
 * 31. 击鼓传花、小孩报数
 */
 function passGame(nameList, num) {
  //1、创建一个队列结构
  let queue = [];
  //2、把学生加入队列
  for (let i = 0; i < nameList.length; i++) {
      queue.push(nameList[i]);
  }
  //3、开始数数
  while (queue.length > 1) {
      //不是这个数，加入队尾
      for (let i = 1; i < num; i++) {
          let n = queue.shift();
          queue.push(n);
      }
      //是这个数,直接删除
      queue.shift();
  }
  //4、获取最后剩下的那个人
  console.log(queue[0]);
}
let winner = passGame([1, 2, 3, 4, 5, 6], 5); // 结果：1

/**
 * 32.promise图片异步加载
 */
function imageAsync(url) {
  return new Promise((resolve, reject) => {
    let img = new Image()
    img.src = url
    img.onload = () => {
      resolve(img)
    }
    img.onerror = err => {
      reject(err)
    }
  })
}